package algorithm;

import java.util.*;

public class T00752 {
    public static void main(String[] args) {
        String[] deadends = new String[]{"0201","0101","0102","1212","2002"};
        String target = "0202";
        System.out.println(new Solution().openLock(deadends, target));
    }

    static class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> deadSet = new HashSet<>(deadends.length);
            Set<String> visited = new HashSet<>();
            for (int i = 0; i < deadends.length; i ++) deadSet.add(deadends[i]);
            Queue<String> queue = new LinkedList<>();
            queue.add("0000");
            int step = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i ++) {
                    String cur = queue.poll();
                    if (visited.contains(cur) || deadSet.contains(cur)) continue;
                    visited.add(cur);
                    if (Objects.equals(cur, target)) return step;
                    for (int j = 0; j < cur.length(); j++) {
                        queue.offer(turnUp(cur, j));
                        queue.offer(turnDown(cur, j));
                    }
                }
                step ++;
            }
            return -1;
        }

        public static String turnUp(String str, int index) {
            char[] arr = str.toCharArray();
            if (arr[index] == '9') arr[index] = '0';
            else arr[index] += 1;
            return new String(arr);
        }

        public static String turnDown(String str, int index) {
            char[] arr = str.toCharArray();
            if (arr[index] == '0') arr[index] = '9';
            else arr[index] -= 1;
            return new String(arr);
        }
    }
}
